#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

string lcs(const string &str1, const string &str2){
    vector<vector<string>> table(str2.size() + 1, vector<string>(str1.size() + 1, ""));
    for(int i = 1; i < table.size(); ++i){
        for(int j = 1; j < table.front().size(); ++j){
            if(str1[j - 1] == str2[i - 1]){
                table[i][j] = table[i - 1][j - 1] + str1[j - 1];
            }
            else{
                if(table[i][j - 1] == table[i - 1][j]){
                    table[i][j] = table[i][j - 1];
                }
                else{
                    table[i][j] = max(table[i][j - 1], table[i - 1][j]);
                }
            }
        }
    }
    return table.back().back();
}

int main(int argc, char const *argv[])
{
    string str1 = "ABC";
    string str2 = "AC";
    cout << lcs(str1, str2) << endl;
    return 0;
}
